1187D - Subarray Sorting - CodeForces Solution

#include <cstdio>
#include <vector>
#include <algorithm>


const int N = int(3e5) + 99;
const int INF = int(1e9) + 99;

int t, n;
int a[N], b[N];
std::vector<int> p[N];
int st[4 * N + 55];


long long getMin(int v, int l, int r, int L, int R) {
    if (L >= R) return INF;
    if (l == L && r == R) return st[v];

    int mid = (l + r) / 2;
    return std::min(getMin(v * 2 + 1, l, mid, L, std::min(R, mid)),
                    getMin(v * 2 + 2, mid, r, std::max(mid, L), R));
}

void update(int v, int l, int r, int pos, int x) {
    if (r - l == 1) {
        st[v] = x;
        return;
    }

    int mid = (l + r) / 2;
    if (pos < mid) update(v * 2 + 1, l, mid, pos, x);
    else update(v * 2 + 2, mid, r, pos, x);

    st[v] = std::min(st[v * 2 + 1], st[v * 2 + 2]);
}


signed main() {

    scanf("%d", &t);
    for (int q = 0; q < t; ++q) {
        scanf("%d", &n);
        for (int i = 0; i < n; ++i) p[i].clear();
        for (int i = 0; i < n; ++i) {
            scanf("%d", a + i);
            --a[i];
            p[a[i]].push_back(i);
        }
        for (int i = 0; i < n; ++i) {
            scanf("%d", b + i);
            --b[i];
        }

        for (int i = 0; i < 4 * n; ++i) st[i] = INF;
        for (int i = 0; i < n; ++i) {
            reverse(p[i].begin(), p[i].end());
            if (!p[i].empty()) update(0, 0, n, i, p[i].back());
        }

        bool check = true;
        for (int i = 0; i < n; ++i) {
            if (p[b[i]].empty()){
                check = false;
                break;
            }

            int pos = p[b[i]].back();
            if (getMin(0, 0, n, 0, b[i]) < pos) {
                check = false;
                break;
            }

            p[b[i]].pop_back();
            update(0, 0, n, b[i], p[b[i]].empty() ? INF : p[b[i]].back());
        }

        if (check) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}